873. Palindromlar

Hərr hansı sözlərdən ibarət, boş olmayan sətir, sağdan sola və əksinə eyni cür oxunursa ona palindrom deyilir.

Kiçik latın hərflərindən ibarət s sözü verilir. Bu sözdən bəzi simvolları pozaraq palindrom almaq olar. Bu sözdən palindromlar almaq üçün neçə üsulla simvollar dəsti (bu dəst boş da ola bilər) silmək lazımdır? Simvolların silinmə ardıcıllığına görə fərqlənən üsullar eyni sayılır.

Giriş. Uzunluğu n (1 ≤ n ≤ 60).olan bir s sətri.

Çıxış. Pozma üsullarının sayını göstərən bir tam ədəd verilir.

Nümunə giriş

BAOBAB

Nümunə çıxış

22

Həlli

dinamik proqramlama

Alqoritmin analizi

Tutaq ki, s_i…s_j alt sətrindən dp[i][j] palindrom almaq olar. O zaman dp[i][i] = 1, çün ki, hər bir hərf özü palindrom sayılır.

Tutaq ki, s_i = s_j = X, s_i…s_j alt sətri XPX kimidir. Burada P ilə s_i+1…s_j-1.alt sətri işarə olunur. XPX palindromunu kəsişməyən qruplara ayıraq:

· Sağ X simvolunu atmaqla alınan say, XP –də alınan say çıx P –dəki palindrom sayı. Yəni, dp[i][j – 1] – dp[i + 1][j – 1];

· Sol X simvolunu atmaqla alınan say, PX –də alınan say çıx P –dəki palindrom sayı. Yəni, dp[i + 1][j] – dp[i + 1][j – 1];

· P sətrinin palindromarı sayı dp[i + 1][j – 1] -yə bərabərdir. Ancaq, P sətrinin hər bir Q palindromu ilə XQX palindromu qura bilərik.

· palindrom XX.

Ümumi palindrom sayı s_i = s_j halı üçün dp[i][j – 1] + dp[i + 1][j] + 1 olar.

İndi qoy s_i ≠ s_j halına baxaq, s_i…s_j alt sətri XPY (s_i = X, s_j = Y) kimidir.. XPY sətrinin palindromlarını kəsişməyən qruplara ayıraq.:

· X simvolu daxildir, Y simvolu daxil deyil. Onların sayı XP sətrindəki palindrom sayı çıx P –dəki palindromların sayı, Yəni, dp[i][j – 1] – dp[i + 1][j – 1];

· Y simvolu daxildir, X simvolu daxil deyil. Onların sayı PY sətrindəki palindrom sayı çıx P –dəki palindromların sayı, Yəni, dp[i + 1][j] – dp[i + 1][j – 1];

· P sətrinin palindromları. Onların sayı dp[i + 1][j – 1] –yə bərabərdir..

Ümumi palindrom sayı s_i ≠ s_j halı üçün dp[i][j – 1] + dp[i + 1][j] – dp[i + 1][j – 1]. olar

Misal

Alqoritmin realizasiyası

Giriş sətrini s massivində saxlayaq. dp massivini yaradaq..

#define MAX 65

char s[MAX];

long long dp[MAX][MAX];

Giriş sətrini oxuyuruq. dp[i][i] = 1 –i doldururuq.

gets(s); n = strlen(s);

memset(dp,0,sizeof(dp));

for(i = 0; i < n; i++) dp[i][i] = 1;

Alt sətirlərin len uzunluqlarını və onların başlanğıc i mövqeyini seçirik.

for(len = 1; len < n; len++)

for(i = 0; i + len < n; i++)

{

j = i + len;

Hər bir s_i…s_j alt sətri üçün dp[i][j] – simvoları silməklə alınan palindromlar sayını hesablayırıq s_i…s_j alt sətri uzunuqların artma sırası ilə baxıldığı üçün bütün kiçik alt sətirlər üçün dp artıq hesabanmış olur.

if (s[i] == s[j])

dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1;

else

dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];

}

Cavabı çixarırıq.

printf("%lld\n",dp[0][n-1]);